package com.zjsru.plan2023.other;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @Author: CookLee
 * @Date: 2023/7/9
 * 从一个范围内选择最多整数 I
 * 给你一个整数数组 banned 和两个整数 n 和 maxSum 。你需要按照以下规则选择一些整数：
 * 被选择整数的范围是 [1, n] 。
 * 每个整数 至多 选择 一次 。
 * 被选择整数不能在数组 banned 中。
 * 被选择整数的和不超过 maxSum 。
 *请你返回按照上述规则 最多 可以选择的整数数目。
 *\
 * 输入：banned = [1,6,5], n = 5, maxSum = 6
 * 输出：2
 * 解释：你可以选择整数 2 和 4 。
 * 2 和 4 在范围 [1, 5] 内，且它们都不在 banned 中，它们的和是 6 ，没有超过 maxSum 。\
 *\
 * 输入：banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
 * 输出：0
 * 解释：按照上述规则无法选择任何整数。
 * \
 * 输入：banned = [11], n = 7, maxSum = 50
 * 输出：7
 * 解释：你可以选择整数 1, 2, 3, 4, 5, 6 和 7 。
 * 它们都在范围 [1, 7] 中，且都没出现在 banned 中，它们的和是 28 ，没有超过 maxSum 。
 *
 */
public class MaxCount {
    
    /**
     * 模拟，会有时间超限的情况,增加了break处理
     *
     * @param banned 禁止
     * @param n      n
     * @param maxSum 马克斯和
     * @return int
     */
    public int maxCount(int[] banned, int n, int maxSum) {
        List<Integer> ansList = new ArrayList<>();
        int sum = 0;
        Set<Integer> set = new HashSet<>();
        for (int num : banned) {
            set.add(num);
        }
        for (int i = 1; i <= n; i++) {
            if (!set.contains(i)) {
                sum += i;
                if (sum <= maxSum) {
                    ansList.add(i);
                }else{
                    break;
                }
            }
        }
        return ansList.size();
    }
    
    public static void main(String[] args) {
        MaxCount maxCount = new MaxCount();
        int[] banned = new int[] {1, 6, 5};
        int n = 5;
        int maxSum = 6;
        System.out.println(maxCount.maxCount(banned, n, maxSum));
    }
}
